1. Field of the Invention
This invention relates to digital transaction systems, and more specifically to secure systems for privacy-protected transfer of certified electronic information based on public key cryptography.
2. Description of Prior Art
The invention relates to electronic systems for privacy-protected transfer of certified information.
It is common usage in the art to model such systems using three basic types of participants: a "certifying" party that certifies information, a "user" that makes use of certified information, and an "organization" to whom certified information is shown. In general, a system will consist of several users and organizations, and possibly also certifying parties. It is also possible for a participant to perform more than one role, such as be a certifying party and an organization or be a user and an organization. Each type of participant has access to an electronic computing device with storage capacity, in the form of, for example, a smart card, a palm-top computer or a personal computer. Certified information is represented by vectors of numbers, hence it can be transferred by electronic means. In this context, a vector is an ordered set of one or more numbers.
A particular example of such a system is an electronic cash system. The certifying party is the blank; it issues money. Users are account holders; they can withdraw electronic money at the bank. Organizations are shops and the like; according to the rules of the system they have to accept certified information as a means of payment for goods and services. Of course, in a practical implementation of such a system there will be various banks and other organizations such as a clearing center.
In general, any transaction system that can be subjected to automation is a potential example of this system. One can consider systems for transferring certified information of a great many types: voting rights, certificates or diplomas, coins, driver's licenses, doctor's approvals, birth certificates, certificates of citizenship, tax-related data, and the like.
It is well-known in the art that digital signatures can be used to certify electronic information. This cryptographic technique consists of the certifying party generating two algorithms or keys, only one of which it makes publicly known. To certify a vector of numbers, the certifying party generates, by applying the secret algorithm, a second vector of numbers (the digital signature) that is in a certain mathematical relation to the vector of numbers to be certified. Two vectors of numbers for which this relation holds can only be efficiently constructed if one knows the secret algorithm. The publicly known algorithm can merely be used to verify whether two vectors of numbers are in such a relation to one another. Hence the second vector can serve as a digital signature on the first vector. Both vectors together form a piece of certified information, and they can be viewed as being one vector embodying a signature of the certifying party.
When digital signatures are used without any additional features, no privacy is offered to the users. Such digital signatures will be referred to as ordinary digital signatures. The information that is shown by users to different organizations can be linked; the certifying party knows which user receives which certified vector of numbers, and the organization that the certified information is transferred to sees exactly the same vector of numbers.
A cryptographic concept has been devised to guarantee privacy in such systems (see U.S. Pat. No. 4,759,063 to Chaum). This concept consists of a so-called "blind" signature protocol between the certifying party and the user. In such a protocol the user can make sure that the certifying party at the end of the protocol has no clue whatsoever regarding the vector of numbers he obtained. Yet, the certifying party knows for sure that the user has obtained a piece of certified information of the type specified at the start of the protocol, such as a coin or a driver's licence.
A second cryptographic concept to guarantee privacy of users when transferring certified information is known. It consists of letting the users be known by different pseudonyms at different organizations such that the pseudonyms are unlinkable. In principle, it is then possible for users to tranfer certified information between their pseudonyms. This concept necessarily uses the concept of blind signature protocols: each user must obtain his pseudonyms in a blind signature protocol. Cryptographic protocols have been proposed that enable the user to transform an ordinary digital signature on one of his pseudonyms (made by the organization at which he has that pseudonym; note that this is an example of an organization acting also as a certifying party) to a digital signature on each of his other pseudonyms. In this way information certified by one particular organization can be shown to all other organizations at which the user has a pseudonym, without enabling the organizations to link the transferred information. A system that makes use of unlinkable pseudonyms between which credentials are transferred is known as a credential mechanism.
Certain types of certified information may only be shown once, such as coins in a cash system. To prevent users in a system based on blind signatures from showing such information multiple times to distinct organizations without ever revealing their identity, a third concept is known, consisting of a special type of blind signature protocol called a "one-show" blind signature protocol (see U.S. Pat. No. 4,914,698 to Chaum). In a one-show blind signature protocol, the certifying party knows for sure that information related to the participating user is encoded into the certified information he obtains. Certified information must then be "tested" by the organization to which it is shown in such a way that testing it twice allows the encoded information to be computed.
To guarantee organizations and certifying parties in the privacy-protecting systems more control over what users do with their certified information, yet another concept is known (see U.S. Pat. No. 4,926,480 to Chaum). This consists of "embedding" a tamper-resistant computing device into the device of the user. Embedding should not to be taken too literally; the configuration might as well consist of, say, a tamper-resistant device connected to the parallel port of the user's personal computer. The tamper-resistant device acts in the interests of the certifying parties and/or organizations. In principle, cryptographic protocols can ensure that the device of the user can only show and erase certified information in cooperation with the embedded tamper-resistant device. Due to the embedding, the user-module can ensure itself that the privacy is guaranteed, since it can see to it that no identity-related information is leaked by or to the embedded device.
Significant difficulties show up in the realization of these concepts. Essentially only one realization of the credential mechanism for transferring credentials between pseudonyms (not considering the few minor variations that have been proposed) is known. In this mechanism, users can transfer a signature on one of their pseudonyms to a signature on all their pseudonyms; there is no provision for transfer between pseudonyms of credentials that may only be used a limited number of times. This is because ordinary digital signatures are used to sign pseudonyms. A further difficulty is that the known realization of a protocol for issuing pseudonyms in a blinded way to users is quite inefficient in communication, computation and storage complexity due to the so-called "cut-and-choose" technique that is applied. Yet another important concern is that the security of this protocol, and hence of the entire system, is an open question. Furthermore, no protocols are known for which the concept of the embedded tamper-resistant part is realized under the most stringent of privacy criteria known in the art, consisting of the impossibility for the certifying party, organization and the tamper-resistant device to develop during the protocols random numbers known to at least two of these parties. No provision seems to exist for multiple users to prove in cooperation that the ensemble of their credentials meets certain requirements. Still another problem is that there seems to be no way for users to prove to an organization that a pseudonym is theirs other than by first obtaining a signature on one of their pseudonyms. Yet another problem is that there seems to be no efficient protocol that can be used to prove that one has a certain combination of a plurality of credentials. A further problem is that it is difficult to allow for credentials that represent quantities, such as age, income, and the like; there is also no provision to prove relations between various quantities without revealing the quantities themselves and no way for certifying parties to update such credentials without needing to know their previous values.
Several realizations of the concepts for the particular instance of off-line electronic cash systems are known. In these systems, one-show credentials are not transferred between pseudonyms; account holders do not have pseudonyms with shops. Yet, this type of system may be called a credential machanism. None of the cash systems known in the literature is a particular instance of the known credential mechanism, i.e., none can be derived from it by using the same general techniques used to realize the credential mechanism. They all use what seem to be ad hoc constructions to realize the concepts of the one-show blind signatures (since coins are credentials that may be shown only once). This causes their security to be an open question, and also prevents efficient implementation by means of a simple and compact software kernel that need not be modified when extensions in functionality are added later on. Furthermore, the withdrawal protocols known to realize the one-show property make use of the cut-and-choose technique, which causes them to be inefficient in communication, computation, and storage complexity. Due to the use of the ad hoc constructions in the protocols, it seems very difficult to extend the functionality of the systems without further worsening the problems related to security and efficiency.
A few extensions allowing the issuing of cheques have been proposed. However, once again, their security is an open problem, and they are quite inefficient. A general technique to incorporate protection against framing attempts of the bank (meaning that the bank falsely accuses an account holder of having double-spent a coin) is known. This technique, however, causes a serious increase in storage requirements for the computing devices of the users and only offers protection assuming that the bank has limited computing power. Another problem is that the only way to encode additional information, such as expiration dates, currency denomination, and the like, seems to be to use a different type of signature for each value. Although it has been suggested that the bank can allow coins to be spent more than once without payments being traceable, no efficient realizations are known. Although untraceable cash systems have been proposed, systems with both untraceable payments and anonymous accounts seem difficult to realize in currently known systems. No system is known that allows realization of the concept of embedded tamper-resistant devices under the most stringent of privacy requirements mentioned above, and the few systems known that realize this extension meeting less stringent criteria have questionable security. Another item of concern might be that there is no satisfactory way to prevent the "halting channel" in this extension. The halting channel problem means that the tamper-resistant part can leak at least one bit of information to the certifying party or organization by simply halting, or not halting, the execution of the protocol at a certain point. In view of these shortcomings, it will come as no surprise that no systems have been proposed that can incorporate all combinations of these extensions simultaneously.
The known credential mechanism and the off-line cash systems that are of practical relevance can all be broken if the so-called RSA problem, well-known in the art (See Rivest et al., "A method for obtaining digital signatures and public-key cryptosystems," Communications of the ACM, Feb. 1978, pp. 120-126), can be broken. No such systems are known that will remain secure even if the RSA problem is broken.